1. Field of the Invention
The present invention relates to information security techniques, and more particularly, to a method and a device that make it possible to hide private information itself while providing system users with prover functions based on the private information in an authentication code system that founds safety on the difficulty of an annihilator determination problem.
2. Prior Art
Decryption keys in the prior art public key cryptography, signature keys in signature, authentication keys in authentication are characteristic information for authenticating the holding of these pieces of private information. As an example, a description will be made of an authentication code system based on an authentication system proposed in xe2x80x9cA practical zero-knowledge protocol fitted to security Microprocessor minimizing both transmission and Memoryxe2x80x9d, Advances in Cryptology EUROCRYPT ""88 (Lecture Notes in Computer Science v.330), C. G. Guenther (ed.), Springer-Verlag pp. 123-128 by Guillou and Quisquater.
FIG. 1 explains the flow of thee authentication code system.
Let n be a composite number that is difficult to factor into prime factors, G be a multiplicative group (Z/nZ)* of a residue class ring of rational integers modulo n, p be a prime number that does not divide Carmichael function xcex(n) of n, R be a space of commitments, xcfx80 be a function from G to R, C be a space of challenge, S be a space of message, xcfx86 be a mapping from a set-theoretic product Cxc3x97S of C and S into Fp (Fp denotes the finite field of p-elements), Ixcex5G be a public verification information, and xxcex5G satisfying Ixp=1 be an authentication characteristic information.
A holder of characteristic information x can send any message Mxcex5S safely because pretending and tampering are prevented by performing the operation of a prover 200 as described below.
(1) Generate a random number kxcex5G and send a commitment r=xcfx80(kp).
(2) Compute an exponent C=xcfx86("khgr",M) by a given challenge "khgr" and a message M to be sent and send the message M and a response s=kxC.
Anyone who can know verification information I can verify the operation of the prover 200 by performing the operation of a verifier 100 as described below, and can assure himself that the prover 200 holds authentication characteristic information and a sent message is not tampered.
(1) After the commitment r is given, send the challenge "khgr" generated at random to the prover 200.
(2) Make sure that the given message M and response s satisfy the following relation.
r=xcfx80(spIxcfx86("khgr",M)xe2x80x83xe2x80x83[Expression 2]
These techniques are developed on the assumption that holders of the above-mentioned private information do not publicize it. Therefore, this allows ciphertext that can be decrypted by only persons holding these pieces of private information, signature that can be generated by only persons holding these pieces of private information, and authentication that makes it impossible for others to impersonate the holders of these pieces of private information.
Accordingly, the above-mentioned techniques can be used in only situations in which exposure of these pieces of private information is disadvantageous to the holders of them. A typical example of such situations is found in a case where the above-mentioned private information is held by only specific individuals and is characteristic information for authenticating the individuals.
In this case, the above-mentioned characteristic information plays a role similar just, to a home lock and an individual""s seal. Practically, the construction of a lock and seal in the actual life as digital information can be easily implemented as a direct application of these cryptographic methods. For example, if a home lock is configured so that it is used as a verifier in the above-mentioned Guillou-Quisquater system and is unlocked only when the verification succeeds, the holding of authentication characteristic information x will be equivalent to the holding of a home lock.
3. Problems of the Prior Art
In contrast to the above-mentioned individual""s home lock case where the exposure of authentication characteristic information is disadvantageous to the individual, there exist cases where the exposure is advantageous to the exposer. These are cases where an holder of characteristic information has the right and qualification to receive specific services. In these cases, an approach cannot be taken which distributes characteristic information representing rights and qualifications to persons having the rights and qualifications and verifies that they hold the characteristic information, as is the above-mentioned case of authenticating individuals. This is because the characteristic information is passed to a third party not having the rights and qualifications since the exposure of the characteristic information is not disadvantageous to the holder of them, so that an advantage can be illegally obtained from the third person.
Hence, heretofore, three types of methods described below have been employed in place of authentication methods employing the above-mentioned public key cryptgraphic techniques without modifications.
(1) A first method is that individuals hold private characteristic information belonging to the individuals and a party to verify the holding of rights and qualifications holds individuals having the rights and qualifications and private characteristic information of the individuals. This method can be used for authentication of rights and qualifications since the leak of characteristic information would be disadvantageous to individuals.
(2) A second method is that individuals hold private characteristic information belonging to the individuals and a party to verify the holding of rights and qualifications holds individuals having the rights and qualifications and public information corresponding to private characteristic information of the individuals. This method can be used for authentication of rights and qualifications since the leak of characteristic information would be disadvantageous to individuals.
(3) A third method is that a grantor of rights and qualifications passes a signature created from characteristic information held by the grantor to a grantee of a right and qualification and a verifier authenticates the right and qualification by verifying the signature. An example of this method is found in xe2x80x9cOnline Cash Checksxe2x80x9d, Advances in Cryptology EUROCRYPT ""89 (Lecture Notes in Computer Science v. 434), J.-J. Quisquater, J. Vandewalle (ed.), Springer-Verlag, pp. 288-293 by D. Chaum.
According to this method, a problem with the leak of characteristic information will not occur since a party to prove the possession of right and qualification has no characteristic information.
However, with the first method, a verifier must hold a list of holders of right and qualification. This imposes the burden of storing and managing the list on the verifier, entailing a high-performance verification device. Also, since the verification device cannot be manufactured independently of the grantor of rights and qualifications, information must be exchanged at all times between the verification device and the grantor of rights and qualifications. Furthermore, since the verifier has individuals"" characteristic information, individuals authenticated by this method will have a risk of the characteristic information being illegally leaked by the verifier.
With the second method, a verifier must hold a list of holders of rights and qualifications. This imposes the burden of storing and managing the list on the verifier, entailing a high-performance verification device. Also, since the verification device cannot be manufactured independently of the grantor of rights and qualifications, information must be exchanged at all times between the verification device and the grantor of rights and qualifications.
With the third method, since distributed signature information can be used by anyone, its duplication must be prevented. This is achieved by a method of preventing duplicate use of a signature value. To be specific, all signature values once used for authentication are stored in the verifier so that the verifier can check that they are not duplicately used. However, to provide this function for the verifier entails a high-performance verification device. Also, all verification devices to authenticate the same rights and qualifications must share a list of signature values once used for authentication, and therefore information must be exchanged at all times among the verification devices.
As described above, any of the three conventional methods contains a serious problem, making it difficult to configure particularly a verifier with small-scale devices and software.
On the other hand, the above-mentioned authentication method that uses characteristic information indicating rights and qualifications is advantageous in that the only task to be done by a verifier is to check to see whether characteristic information indicating rights and qualifications is held.
As described above, the prior art has been a problem in that if a small-scale verification device is used to authenticate rights and qualifications, there may arise a risk of authentication characteristic information leaking to outsiders, while if the risk is to be eliminated, the verification device becomes large-scale.
As described above, an object of the present invention is to implement an authentication code technique which enables a small-scale verification device to authenticate rights and qualifications without authentication characteristic information leaking to outsiders.
An authentication code technique of the present invention is based on:
(1) an interaction device that generates document private information from a document, which is releasable information defined at ticket issuance, and makes interaction based on the document private information, and
(2) a ticket, which is releasable information generated from the document private information and authentication characteristic information.
That is, according to the present invention, where p is a prime number, Fp is a p-element field, G is a finite Abelian group (described multiplicatively only for the purpose of fixing a notation. The present invention can also apply to groups customarily described additively, e.g., an elliptic curve, if it is difficult in point of computational complexity to obtain an annihilator) whose annihilator is difficult in point of computational complexity to obtain, R is a space of commitments, xcfx80 is a mapping from G to R, and C is a space of challenges, S is a space of messages, xcfx86 is a mapping from a set-theoretic product Cxc3x97S of C and S into Fp, the following steps are executed in an interaction method by which commitment r is generated, and response "sgr" and message M are generated for document m and challenge "khgr".
(a) Step to generate nonreproducible private information kxcex5G at random
(b) Step to compute commitment r=xcfx80 (kp)
(c) Step to compute document private information xcexc=f (m) with f as a private function with valued in G
(d) Step to generate message M
(e) Step to compute exponent C=xcfx86("khgr",M)
(f) Step to compute response "sgr"=kxcexcC 
In this configuration, proof functions based on authentication characteristic information can be distributed without disclosing the authentication characteristic information in public key cryptography. Hence, it has become possible for a plurality of individuals having no interest with each other to safely perform proving based on identical authentication characteristic information. This has been heretofore impossible. Since public key cryptography based on Guillou-Quisquater authentication is employed, zero knowledgability is proved. Moreover, messages can be safely transferred.